/*
 *https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/
 *600. 不含连续1的非负整数
 *difficult 吴朝泽 2024.9.20
 *数位DP
 与 lc233 类似，不同之处在于本题求解的是二进制下的数中不含连续 1 的数字个数，
 要注意在取每一位数的时候是取模于 2 ，并且每次除以 2
*/


class Solution {
public:
    int arr[100];   //存储每一位的数字
    long long dp[30][30];    //用于记忆化搜索，存储状态

    //pos 表示当前位数，pre 表示上一位填的数字，flag 表示填的数字大小是否受到限制
    long long DFS(int pos, int pre, bool flag)
    {
        //如果位置为 0 直接返回
        if(pos == 0)  return 1;    

        //如果没有限制且前一位数有效，并且 dp[pos][pre] 已经被计算过就直接返回
        if(!flag && pre >= 0 && dp[pos][pre] != -1)  return dp[pos][pre];

        //判断最大的数可以是多少，如果 flag 不成立就是 0和1 都可以，否则当前位的数就是最大数
        int max_num = flag ? arr[pos] : 1;

        long long res = 0;
        for(int i = 0; i <= max_num; ++i)
        {
            //如果当前位数填的数字是 1 且上一位数填的数字也是 1 ，跳过不计数
            if(i == 1 && pre == 1)  continue;
            res += DFS(pos-1, i, flag && (i == max_num));
        }

        if(!flag)  dp[pos][pre] = res;
        return res;
    }

    //将传进来的十进制整数转换为二进制并且获得二进制的每一位是多少存储在 arr 数组里，
    //记得 arr[1] 代表二进制数的最低位即第一位
    long long check(long long x)
    {
        int pos = 0;
        while(x)
        {
            arr[++pos] = x % 2;
            x /= 2;
        }
        return DFS(pos, 0, 1);   //pos 依旧从最高位开始
    }

    int findIntegers(int n) 
    {
        memset(arr, 0, sizeof(arr));
        memset(dp, -1, sizeof(dp));
        return check(n);
    }
};